package com.zlk.algorithm.algorithm.dynamicPlan.arraySum.more;

import org.junit.Test;

// 乘积最大子数组
// 给你一个整数数组 nums
// 请你找出数组中乘积最大的非空连续子数组
// 并返回该子数组所对应的乘积
// 测试链接 : https://leetcode.cn/problems/maximum-product-subarray/
public class Code01_MaximumProductSubarray {


    @Test
    public void test(){
        System.out.println(maxProduct(new int[]{2, 3, -2, 4}));
    }


    // dp[i] 表示i位置结尾的最大子数组乘积
    // 1、dp[i-1] max * nums[i]
    // 2、dp[i-1] min * nums[i]
    // 3、 nums[i]
    public int maxProduct(int[] nums) {
        int premin = nums[0];
        int premax = nums[0];
        int ans = nums[0];
        for (int i = 1,curmin, curmax; i < nums.length; i++) {
            curmax = Math.max(Math.max(premax*nums[i],nums[i]),premin*nums[i]);
            curmin = Math.min(Math.min(premax*nums[i],nums[i]),premin*nums[i]);
            premax = curmax;
            premin = curmin;
            ans = Math.max(premax,ans);
        }
        return ans;
    }
}
